/*
https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/description/
*/

-------------------------------------------------------------------------
class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1; // 节点总数等于边数加1
        vector<int> e[n]; // 邻接表表示的图

        // 构建图
        for (auto &r : roads) {
            int x = r[0], y = r[1];
            e[x].emplace_back(y);
            e[y].emplace_back(x);
        }

        long long ans = 0; // 最小燃料成本

        // 深度优先搜索函数，返回以当前节点为根的子树的大小
        function<int(int, int)> dfs = [&](int x, int fa) -> int {
            long sz = 1; // 当前子树的大小，至少包含根节点自己
            for (int nx : e[x]) {
                if (nx != fa) { // 不访问父节点
                    int t = dfs(nx, x); // 递归获取子树大小
                    // 计算从子树到当前节点的燃料成本，并累加到总成本中
                    ans += (t + seats - 1) / seats;
                    sz += t; // 更新当前子树的大小
                }
            }
            return sz; // 返回子树大小
        };

        dfs(0, -1); // 从根节点开始遍历，-1表示没有父节点
        return ans; // 返回最小燃料成本
    }
};
------------------------------------------------------------